package com.leet.code.simple_array;

import java.util.HashSet;
import java.util.Set;

/**
 * @description:    1346.检查整数及其两倍数是否存在
 * @author: WYG
 * @time: 2021/1/2 9:34
 */

public class CheckIfExist {

    public boolean checkIfExist(int[] arr) {
        //双重for循环判断是否存在2倍元素
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == 2 * arr[j] || arr[j] == 2 * arr[i]) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean new_checkIfExist(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int value : arr) {
            //如果集合中包含这个数说明存在它的2倍,返回true
            if (set.contains(value)) return true;
            //如果集合中不包含这个数,那么将这个数的2倍加如集合中,这就对应第一个判断
            set.add(value * 2);
            //如果这个数是偶数,那么将这个数的1/2放入数组中,这就对应第一个判断
            if ((value % 2) == 0) set.add(value / 2); // 能整除才放入
        }
        return false;
    }
    /*
    先将所有数字存入哈希表，再遍历所有的数字 x，判断 2x 是否在哈希表中。注意数字 0 需要特殊考虑。可以通过计数来解决数字 0 的问题：若x!=0，
    则 2x只需要出现一次，否则需要出现两次。对于 Java 代码，由于数字范围是 [-1000， 1000]，2x 的范围为 [-2000， 2000]我们只需要创建一个长度为
    4001 的数组 hash_set。为了解决下标为负时越界的问题，我们使用hash_set[i+2000]来避免下标越界。
     */
    public boolean fast_checkIfExist(int[] arr) {
        int[] hash_set = new int[4001];
        for (int n : arr)
            ++hash_set[n + 2000];
        for (int n : arr)
            if (n != 0 && hash_set[2 * n + 2000] >= 1)
                return true;
            else if (n == 0 && hash_set[2 * n + 2000] >= 2)
                return true;
        return false;
    }
}
